The invention relates generally to communication systems, and more particularly to scheduling for bandwidth allocation in a shared medium communication network that employs a contention-based reservation mechanism for coordinating channel access.
Communication networks and technologies have been evolving rapidly to meet current and future demands for efficient remote information exchange and high-speed Internet access. In some communication networks, referred to as shared medium networks, transmission resources are shared among a population of users. In a shared medium network, users independently access the network via stations, and uncoordinated transmissions from different stations may interfere with one another. Such a network typically includes a number of secondary stations that transmit on the shared channel, and a single primary station situated at a common receiving end of the shared channel for, among other things, coordinating access by the secondary stations to the shared channel.
Protocols that are employed to coordinate access to a shared channel are often referred to as Medium Access Control (MAC) protocols. MAC protocols fall into two basic categories: contention-based and contention-free protocols. In contention-based protocols, end users contend with one another to access channel resources. Collisions are not avoided by design, but are either controlled by requiring retransmissions to be randomly delayed, or resolved using a variety of other contention resolution strategies. In contention-free protocols, end users access a shared channel in a controlled manner such that transmissions are scheduled either statically, or adaptively so that collisions are completely avoided.
An example of a contention-based MAC protocol is known as an Aloha protocol. Its original version, which operates with continuous or unslotted time is referred to as Unslotted Aloha. The behavior and performance of Unslotted Aloha have been studied widely, and its maximum throughput is well known to be 1/(2e). A later version of the Aloha protocol, which operates with discrete or slotted time, is referred to as Slotted Aloha. Many variations and extensions have been derived from the original Slotted Aloha protocol. In this protocol, and most of its derivatives, provided the probability of a new transmission and that of a retransmission in each slot are small, the throughput in a slot can be approximated by G(n) exp{xe2x88x92G(n)}, where G(n) is the offered load or attempt rate i.e., the number of packet arrivals per packet transmission opportunity, which is a function of n that denotes the number of backlogged users at the beginning of a given time slot. It follows that the maximum throughput of Slotted Aloha is 1/e=0.368, which is attained when G(n)=1, i.e. one packet arrival per packet transmission opportunity. The constant e is the base for natural logarithm. It is to be noted that the value 1/e reflects the efficiency of Slotted Aloha, as it indicates on the average one successful packet transmission every e packet transmission opportunities.
Most contention-based protocols, including the Aloha protocols, resolve collisions by using feedback information on the number of users involved in the collisions. Based on this feedback information, each backlogged user executes a predetermined back off strategy to ensure stable operation of the protocol. In practice, feedback information used is typically ternary indicating zero, one, or more transmissions, or binary indicating exactly one transmission or otherwise.
It is well known that ordinary Slotted Aloha is unstable. Various methods for stabilizing Slotted Aloha exist, and many of them resort to adaptive control of the back off scheme based on one or more states of the contention process. When the actual values of these states are not observable, they are estimated by a variety of means. The stability of Slotted Aloha can be controlled by means of a dynamic frame structure, based on an a posteriori expected value of the backlog at the beginning of each frame. Rivest proposed a Pseudo-Bayesian algorithm to maintain the attempt rate G(n) close to 1 by estimating the number, n, of backlogged users at the beginning of each slot (Rivest, xe2x80x9cNetwork Control by Bayesian Broadcast,xe2x80x9d technical report MIT/LCS/TM-287, MIT Lab. for Computer Science, 1985). A minimum mean-squared error predictor for estimating the channel backlog in Slotted Aloha was proposed by Thomopoulos for regulating the retransmission probability according to a recursive function of the channel backlog estimate (Thomopoulos, xe2x80x9cA Simple and Versatile Decentralized Control for Slotted Aloha, Reservation Aloha, and Local Area Networks,xe2x80x9d IEEE Trans. on Communications, Vol. 36, No. 6, June 1988).
In a contention-free multiple access protocol with static scheduling, such as that of a Time Division Multiple Access (TDMA) scheme, a predetermined transmission pattern is repeated periodically. The users may access channel resources only during the time intervals assigned to them individually. Contention-free protocols with static scheduling for resource allocation are inefficient for supporting a large population of users where, typically, only a fraction of the users are active at any time. In a contention-free multiple access protocol with adaptive scheduling, the transmission pattern may be modified in each cycle, via reservation, to accommodate dynamic traffic demand. A reservation scheme typically requires a centralized controller to manage reservations. A fraction of the channel, or a separate channel, is often used to support the overhead due to reservation.
It has been known that reservation protocols with contention-based transmission of request messages are particularly suitable for a shared medium communication system in which there is a large population of bursty users with long messages. This is the case in a Hybrid Fiber Coaxial Cable Network with a Cable TV headend coupled through an optical fiber mode to a two way coaxial amplifier to which are attached a number of cable modems.
In the prior art, the channel is modeled as a stream of transmission slots of a fixed size. The channel is divided into frames, wherein the number of transmission slots in each frame is fixed. Each frame consists of a contention interval, and a data interval. Each contention interval contains a number of contention slots that are allocated for contention-based transmission of reservation packets in accordance with the Slotted Aloha protocol. Each reservation packet carries appropriate control information including the number of data slots requested. Each data interval contains a number of data slots that are allocated for transmission of reserved data packets. Depending on the granularity of the transmission slots, a contention slot may be an integral fraction of a transmission slot or an integral multiple of a transmission slot. Typically, the granularity of the transmission slots is selected such that a data slot is either a single transmission slot or an integral multiple of a transmission slot. In any case, a contention slot is typically much smaller than a data slot.
Szpankowski teaches a frame-based contention-based reservation system, wherein Slotted Aloha is used to coordinate transmission of reservation requests and each successful request transmission in a frame reserves a data slot in a data interval of a future frame. In accordance with the teaching of Szpankowski, provided the sizes of each frame and the two intervals in it are respectively fixed, system throughput in the steady state is maximized when the ratio of the number of data slots in each frame to the number of contention slots in the same frame is equal to 1/e, which is the throughput of Slotted Aloha (Wojciech Szpankowski, xe2x80x9cAnalysis and Stability Considerations in a Reservation Multiaccess System,xe2x80x9d IEEE Trans. Communications, Vol. COM-31, No. 5, May 1983). In other words, the number of contention slots allocated in a frame must be such that the ratio of the number of data slots allocated in the frame to the number of contention slots in the frame is 1/e, i.e., the efficiency of Slotted Aloha.
Dail, et al., teach a method for a headend to dynamically adjust the number of mini-slots (corresponding to contention slots) over a period of time as a function of the type, or mix, of communications traffic. This dynamic allocation therefore does not adapt to changing request offered load. The dynamic allocation does however depend upon the traffic mix, which includes contention-type traffic (e.g., bursty traffic) that requires contention-based reservation and reservation-type traffic (e.g., isochronous traffic) that is allocated transmission opportunities without the need for contention-based reservation (J. Dail, C. Li, P. Magill, and K. Sriram, xe2x80x9cMethod and Apparatus Enabling Enhanced Throughput Efficiency by Use of Dynamically Adjustable Mini-Slots in Access Protocols for Shared Transmission Media,xe2x80x9d U.S. Pat. No. 5,953,344, Sep. 14, 1999). Specifically, the method considers a frame-based system with data slots of a fixed size, wherein the data slots in each frame are divided among contention-type traffic and reservation-type traffic, such that reservation-type traffic takes priority over contention-type traffic. In accordance with the method of Dail, et al., given the number of data slots needed for the transmission of reservation-type data packets in each frame, the remaining number of data slots in the frame are to be allocated for transmission of contention-type data packets as well as the contention-based request packets that are used for reserving data slots for contention-type traffic. Since request packets are typically considerably smaller than data packets, the data slots used for transmission of request packets are converted to mini-slots for contention usage. The teaching of Dail, et al., is based on the assumption that each mini-slot resolves contention requests at the same efficiency as a Slotted ALOHA system, i.e., each mini-slot has a throughput efficiency of 1/e. For practical reasons, Dail, et al., further assume that this efficiency is scaled down by about 90%, so that it is about ⅓. Specifically, Dail, et al., teach that the number of contention mini-slots allocated in a frame must be such that the ratio of the average number of contention-type messages that are allocated data slots in the frame to the number of mini-slots in the contention interval of the frame is ⅓. The method of Dail, et al., allows the number of data slots that may be reserved for each contention-type message to be a random number with a predetermined average value. It is to be noted that the method of Dail, et al., is in essence a straightforward extension of Szpankowski""s method as described before.
Golmie, et al., have considered a slight variation of the method of Dail, et al. (N. Golmie, et al., xe2x80x9cA Review of Contention Resolution Algorithms for IEEE 802.14 Networks,xe2x80x9d IEEE Communication Surveys, 1999). Likewise, while the method of Golmie, et al., does not dynamically depend upon request offered load, but on traffic mix, in their approach, the ratio of the average number of contention-type messages that are allocated data slots in a frame to the number of mini-slots in the contention interval of the frame is xc2xd, instead of ⅓, and no contention slot is allocated when the number of data slots pending allocation exceeds 2.5 times the remaining number of data slots in the frame. Similarly to the method of Dail, et al., the method of Golmie, et al., focuses on the changing data offered load of the reservation-type traffic, but not on the changing request offered load of the contention-type traffic.
In a frame-based system, each frame in a contention-based reservation system is often constrained by a minimum frame size. In some cases, this constraint is due to a maximum round trip delay in the system, wherein a minimum frame size that is greater than the maximum round trip delay enables all users who transmitted request messages in a frame to receive feedback in time for retransmission in the contention interval of the next frame if necessary. In other cases, the constraint is due to limits on processing capacity in the headend, which dictates a maximum frame scheduling frequency.
There may be leftover slots when there is not enough data to utilize the available slots in a frame of a minimum size. There may also be leftover slots if packets are not permitted to be fragmented in order to pack a frame completely. When there are leftover slots that cannot be used for data transmission, they may be utilized for other purposes. For example, leftover slots in a frame may be included in the contention interval of the frame for contention-based transmission of request messages.
It is to be noted that if the headend is able to process scheduling on a slot by slot basis, then bandwidth allocation in a slotted shared medium network does not have to be frame-based. However for Hybrid Fiber Coaxial Cable Networks, information is transmitted on a frame-by-frame basis in accordance with the DOCSIS protocol. Sala, et al., teach a slot-based system based on a frameless MAC protocol, wherein contention opportunities are inserted continuously as they are needed, based on a predetermined contention slot allocator that allocates contention slots to accommodate an estimated demand for contention access (Dolors Sala, John O. Limb, and Sunil U. Khaunte, xe2x80x9cAdaptive Control Mechanism for Cable Modem MAC Protocols,xe2x80x9d Proceedings of IEEE INFOCOM ""98, Mar. 29-Apr. 2, 1998). The method follows a strategy that allocates for contention-based reservation all slots that are not being used for data transmission. The number of contention opportunities allocated per data slot is derived by maximizing steady state contention throughput.
In accordance with the teaching of Sala, et al., when there is negligible round trip delay in the network, contention opportunities will continuously be allocated until there is a successful request transmission, and each successful request transmission will be followed by the transmission of a data packet. Non-zero round trip delay lowers the effectiveness of the method for additional contention opportunities will be allocated from the time a request is successfully transmitted until the time the corresponding reserved data slots are allocated. At low data load, since there is plenty of unused bandwidth that could be used for contention reservation, many more contention opportunities than the number required for stable operations are allocated. The surplus of contention opportunities reduces the probability of collision to a very low level, which in turn reduces contention access delay. As data load increases, the method converges to allocating an average of e (about 2.7183) contention opportunities per data slot.
The above prior art gives priority to reserved data slots over contention opportunities. No contention opportunities are allocated unless all reserved data slots have been allocated. This policy can result in high contention access delay when the data offered load is high. Sala, et al., offers a method for improving the performance of the contention slot allocator, wherein a dynamically determined number of contention opportunities are forced between data slots, in addition to the unreserved contention opportunities. This number of forced contention opportunities is based on an approximation of the number of contention opportunities required to maximize contention throughput in accordance with the Slotted Aloha model, wherein the product of the average number of packets per data message and the number of forced contention opportunities is equal to e. It is to be noted that the teaching of Sala, et al., follows the same spirit of the teaching of Szpankowski, in the sense that the number of forced contention opportunities in an extended period of time must be such that the number of data messages that may be transmitted within that period is equal to the expected number of successful request transmissions in the forced contention opportunities within the same period, wherein the expected number of successful request transmissions in the forced contention opportunities in a given period is given by the product of the number of contention opportunities within the period and 1/e, i.e., the efficiency of Slotted Aloha.
A mechanism, known as piggybacking, is sometimes used to decrease the contention offered load when the system is operating with high data load. With piggybacking, a request that would otherwise require contention access could be inserted in a data packet to reserve additional data transmission slots. In this respect, upstream bandwidth utilization is more efficient due to reduced contention overhead. When there is piggybacking, the number of forced contention opportunities is thus scaled down by a factor that accounts for the piggyback load.
With respect to all of the above fixed frame systems, not one takes into account differing or changing request offered loads. Without taking into account the request offered load on a dynamic basis one cannot allocate bandwidth dynamically to optimize with respect to certain performance objectives, including contention access delay, data scheduling delay, and a trade-off between them. Contention access delay is the time from the generation of a request to reserve mini-slots for transmission of the data packet to the time the request is successfully transmitted and accepted by the headend. Data scheduling delay is the delay from the time the request is accepted by the headend to the time the data packet is completely transmitted on the channel.
Tasaka and Ishibashi have studied the performance and stability conditions of a contention-based reservation protocol (S. Tasaka and Y. Ishibashi, xe2x80x9cA Reservation Protocol for Satellite Packet Communicationxe2x80x94A Performance Analysis and Stability Considerations,xe2x80x9d IEEE Trans. Communications, Vol. COM-32, No. 8, August 1984). They have devised a procedure for determining an optimum set of system parameters for stable operation of the system, given an offered load, such that the average message delay is minimized, wherein the set of system parameters include the numbers of transmission slots in the contention interval and the data interval. Given the offered load, the procedure determines, for each combination of the numbers of transmission slots in the contention interval and the data interval, a probability of retransmission in each frame such that the average message delay is minimized. This step is repeated for a sufficiently large number of combinations of the numbers of transmission slots in the contention interval and the data interval, until a global minimum of the average message delay can be determined. It is to be noted that this method is computationally involved, and it is not clear how one would know when the global minimum of the average message delay is actually attained.
With respect to one shared medium network, a multiple access protocol with contention-based reservation may be applied to bandwidth allocation in an upstream channel of a Hybrid Fiber-Coaxial (HFC) cable network. The primary station in the cable network, which is often referred to as a headend, is basically a centralized controller that allocates upstream bandwidth to a group of secondary stations, which are often referred to as cable modems. This is accomplished by transmitting downstream a control message containing an information element known as a MAP. Each MAP specifies the allocation of transmission opportunities in a transmission frame that consists of a group of contiguous slots in the upstream channel. Each frame is divided into a contention interval for contention-based reservation and a data interval for data transmission. Secondary stations with data to send transmit requests in the Contention interval to reserve for transmission opportunities in data intervals of future frames. The outcomes of contention depend on the request offered load in terms of the number of requests generated per slot. Each transmission opportunity within a contention interval may end up with no request transmitted in it (Idle), one request transmitted in it (Success), or multiple requests transmitted in it (Collision). The headend provides a positive acknowledgment in a future MAP to each user with a successful request transmission. A successful transmission of a request from a secondary station reserves a data transmission opportunity in a future frame for the secondary station. A secondary station whose request transmission is not acknowledged in a future MAP after a predetermined amount of time is required to backoff for some time before retransmitting the request. A typical procedure used for collision resolution is truncated binary exponential backoff, wherein a backoff window limits the range of random backoff, and an initial backoff window is doubled in successive attempts for retransmission. As the binary exponential backoff approach is known to lead to instability in heavy load, a maximum number of retransmissions for a request is imposed to terminate the otherwise indefinite backoff.
As will be appreciated, a need remains for a simple method and a device for allocating bandwidth dynamically to adapt to changing request offered load in a contention-based reservation protocol used in a slotted shared medium communication network, wherein transmission slots are allocated on a frame by frame basis. As noted above, a frame-based system is specified by the DOCSIS protocol, and it is desirable to efficiently allocate bandwidth in the:upstream channel of the HFC cable network, while minimizing overall message delay, which consists of contention access delay and data scheduling delay.
In the subject system, which is a frame-based contention-based reservation system, the dividing line between slots allocated for contention and data in each frame is ascertained by taking into account request offered load as well as data offered load. Request offered load means the number of requests generated per slot. Data offered load is reflected in the number of slots reserved by each successfully transmitted request.
In accordance with the present invention, the population of users collectively and randomly generate requests with an offered load that is quasi-static, i.e., the request offered load may change slowly with time. In the operation of a frame-based contention-based reservation system, when a request is generated in a given frame, it must wait until the next frame before it is eligible for transmission. It is to be noted that the request offered load in a given frame translates to an effective request offered load in the contention interval of the following frame. The request offered load may be known a priori, or estimated as proposed in a prior art by Abi-Nassif, et al. (F. Abi-Nassif, W. C. Lee, and I. Stavrakakis, xe2x80x9cOffered Load Estimation in a Multimedia Cable Network System,xe2x80x9d IEEE ICC ""99, Vancouver, Jun. 6-10, 1999).
Note that unlike prior frame-based systems in which request offered load is taken to be static, the dynamic nature of the request offered load in the subject system determines the number of slots allocated for the contention and data intervals. This system thus allocates the number of slots for contention and data in each frame to optimize with respect to certain performance objectives, including contention access delay, data scheduling delay, and a trade-off between them.
It will be appreciated that although the subject system considers each frame to possibly have a different size, it is obviously applicable when frame size is fixed. In one embodiment of the invention, the system takes into consideration the changing request offered load in allocating the number of slots for contention and data in each frame to maximize contention throughput. It will be appreciated that such allocation minimizes the chance for the contention-based reservation system to become unstable, i.e. the number of slots allocated for contention is not sufficient to serve all backlogged requests timely, thereby enabling the system to operate with bounded contention access delay.
In another embodiment, the system allocates the number of slots for contention and data in each frame to maximize contention throughput when the system is overloaded, i.e., excessive request offered load, and otherwise guarantees a fixed minimum number of slots for contention. It will be appreciated that such allocation not only minimizes the chance for the contention-based reservation system to become unstable, but also lowers contention access delay at minimal expense of data scheduling delay when the system is non-overloaded.
In yet another embodiment, the system allocates the number of slots for contention and data in each frame to maximize contention throughput when the system is overloaded, and otherwise balances supply and demand of slots for data transmission, wherein the demand is a function of request offered load and data offered load. It will be appreciated that such allocation not only minimizes the chance for the contention-based reservation system to become unstable, but also minimizes contention access delay while ensuring that data scheduling delay is bounded when the system is non-overloaded.
All the above embodiments take into account the changing request offered load. The subject system initially makes a tentative allocation in the contention interval, such that the allocation is bounded from below by the allocation that maximizes contention throughput. Should there be any leftover slots in the frame after allocating the remaining slots for data transmission, the leftover slots are included in the contention interval of the frame. There may be leftover slots because there may not be enough reserved slots pending allocation to fill up the remainder of the frame, or there may not be a perfect fit of data slots in the remainder of the frame.
The second and third embodiments further take into account the average number of slots reserved per successfully transmitted request as well as the desired utilization of a data scheduler, which is used to allocate slots in data intervals among user data flows. It will be appreciated that the number of slots reserved per successfully transmitted request reflects the data offered load in the system, and the desired utilization of the data scheduler dictates an upper-bound on data scheduling delay for a given data scheduler. It will be appreciated that the present invention does not depend on any specific data scheduler design, but on the desired utilization of the data scheduler. In general, data scheduling delay increases with the utilization of the data scheduler, and typically increases without bound as utilization approaches 1. In practice, one would set the utilization of the data scheduler to a value close to one, but leave enough room such that data scheduling delay can be bounded as desired.
The subject system makes use of a supply and demand model in which the demand depends upon the request offered load. In this system, an appropriate size for a contention interval in each upstream transmission frame is determined by attempting to balance the rates of flow of user data.into and out of a virtual global data queue, wherein a fluid approximation method is used that is based on a solution to a balanced equation relating the demand and supply of slots. In normal non-overload operation, the system initially makes a tentative allocation in the contention interval, such that the allocation is bounded from above by the solution to the balanced equation. Whenever the system is undergoing transient overload, the subject system allocates slots in the contention interval to maximize contention throughput. In any case, should there be any leftover slots in the frame after allocating the remaining slots for data transmission, the leftover slots are included in the contention interval of the frame.
In summary, the problem of allocating bandwidth on the upstream channel of an HFC cable network for contention-based transmission of requests that are used to reserve upstream bandwidth for transmission of user data is solved by a method of allocation which dynamically adapts to the prevailing offered load of reservation requests. In a preferred embodiment, this is done by determining an appropriate size for a contention interval in each upstream transmission frame by attempting to balance the rates of flow of user data into and out of a virtual global data queue using a fluid approximation method that is based on a solution to a balanced equation relating the demand and supply of slots for data transmission within each frame.